// 二叉树
#ifndef BIN_TREE_H
#define BIN_TREE_H

/// @brief 二叉树结构体
typedef struct BTNode
{
	char data;					 // 节点值
	struct BTNode *left, *right; // 节点左孩子和右孩子指针
} BTNode, *BinaryTree;

// @brief 树结构体
typedef struct MTNode
{
	char data;								 // 节点值
	struct MTNode *firstChild, *nextBrother; // 结点的第一个孩子结点和下一个相邻的兄弟结点的指针
} MTNode, *Tree;

/// @brief 通过终端的标准输入来构建一个二叉树，输入一个节点字符回车一次，若当前节点为空则连按两次回车
/// @param tip 提示信息
/// @return 二叉树的根节点指针（二叉树对象）
BinaryTree createTreeByScanf(char[]);

/// @brief 通过数组元素来构建一个二叉树，按照层次遍历方式
/// @param i 取数组中下标为i的元素构造节点
/// @param n 数组长度
/// @param datas 存放所有根节点值的数组
/// @return 二叉树的根节点指针（二叉树对象）
BinaryTree createTreeByArray(int, int, char[]);

/// @brief 查找目标字符在字符串中的位置
/// @param target 目标字符
/// @param datas 字符串
/// @return 目标字符所在下标，不存在返回-1
int indexOf(char, char[]);

/// @brief 根据前序遍历和中序遍历来创建二叉树
/// @param preOrder 前序遍历序列
/// @param preStart 前序序列的开始读取下标
/// @param preEnd 前序序列的终止读取下标
/// @param inOrder 中序遍历序列
/// @param inStart 中序序列的开始读取下标
/// @param inEnd 中序序列的终止读取下标
/// @return 二叉树的根节点指针（二叉树对象）
BinaryTree createTreeByPreOrderAndInOrder(char[], int, int, char[], int, int);

/// @brief 根据后序遍历和中序遍历来创建二叉树
/// @param postOrder 后序遍历序列
/// @param postStart 后序序列的开始读取下标
/// @param postEnd 后序序列的终止读取下标
/// @param inOrder 中序遍历序列
/// @param inStart 中序序列的开始读取下标
/// @param inEnd 中序序列的终止读取下标
/// @return 二叉树的根节点指针（二叉树对象）
BinaryTree createTreeByPostOrderAndInOrder(char[], int, int, char[], int, int);

/// @brief 树转换为二叉树
/// @param tree 原始普通树状结构
/// @return 二叉树
BinaryTree treeToBinaryTree(Tree);

/// @brief 打印二叉树先序遍历结果（递归）
/// @param tree 二叉树对象
void preorderTraverse(BinaryTree);

/// @brief 打印二叉树先序遍历结果（非递归）
/// @param tree 二叉树对象
void preorderTraverseNonRecursion(BinaryTree);

/// @brief 打印二叉树中序遍历结果（递归）
/// @param tree 二叉树对象
void inorderTraverse(BinaryTree);

/// @brief 打印二叉树中序遍历结果（非递归）
/// @param tree 二叉树对象
void inorderTraverseNonRecursion(BinaryTree);

/// @brief 打印二叉树后序遍历结果（递归）
/// @param tree 二叉树对象
void postorderTraverse(BinaryTree);

/// @brief 打印二叉树后序遍历结果（非递归）
/// @param tree 二叉树对象
void postorderTraverseNonRecursion(BinaryTree);

/// @brief 打印二叉树层次遍历结果
/// @param tree 二叉树对象
void hierarchicalTraverse(BinaryTree);

/// @brief 计算二叉树节点数量
/// @param tree 二叉树对象
/// @return 二叉树结点数
int nodeCount(BinaryTree);

/// @brief 计算二叉树叶子节点数
/// @param tree 二叉树对象
/// @return 二叉树叶子节点数
int leafCount(BinaryTree);

/// @brief 计算二叉树非叶子节点数
/// @param tree 二叉树对象
/// @return 二叉树非叶子节点数
int notLeafCount(BinaryTree);

/// @brief 计算二叉树单分支节点数
/// @param tree 二叉树对象
/// @return 二叉树单分支节点数
int singleBranchCount(BinaryTree);

/// @brief 计算二叉树双分支节点数
/// @param tree 二叉树对象
/// @return 二叉树双分支节点数
int doubleBranchCount(BinaryTree);

/// @brief 计算传入节点的子孙数
/// @param node 传入的二叉树节点指针
/// @return 这个节点的子孙数
int childCount(BTNode *);

/// @brief 计算二叉树的高度
/// @param tree 二叉树对象
/// @return 二叉树高度
int treeHeight(BinaryTree);

/// @brief 计算二叉树的宽度
/// @param tree 二叉树对象
/// @return 二叉树宽度
int treeWidth(BinaryTree);

/// @brief 普通树状结构的高度
/// @param tree 树对象
/// @return 树的高度
int normalTreeHeight(Tree);

/// @brief 在排序二叉树中寻找对应的节点
/// @param tree 待查找的排序二叉树
/// @param parent tree节点的双亲节点，若tree为根节点传入NULL即可
/// @param data 待查找的节点值
/// @return 对应节点值的节点指针，若找不到对应的值的节点则返回查找过程中的最后一个叶子结点指针
BTNode *searchSortTree(BinaryTree, BTNode *, int);

/// @brief 在二叉排序树中插入节点
/// @param tree 二叉排序树
/// @param data 要插入的节点值
void insertSortTree(BinaryTree, int);

/// @brief 创建一个二叉排序树
/// @param nodes 节点值
/// @param n 节点数量
/// @return 二叉排序树
BinaryTree createSortTree(int[], int);

/// 判断是否为二叉排序树
/// @param tree 二叉树对象
/// @return 是否是二叉排序树
int isSortTree(BinaryTree);

/// @brief 判断是否为完全二叉树
/// @param tree 二叉树对象
/// @return 是否为完全二叉树
int isComplete(BinaryTree);

/// @brief 判断是否为平衡二叉树
/// @param tree 二叉树对象
/// @return 是否为平衡二叉树
int isBalance(BinaryTree);

/// @brief 查找某个值的节点
/// @param tree 二叉树对象
/// @param data 待查找节点值
/// @return 节点指针，若没找到则返回NULL
BTNode *getNode(BinaryTree, char);

/// @brief 判断一个二叉树是否和另一个二叉树完全相同
/// @param tree1 第一个二叉树
/// @param tree2 第二个二叉树
/// @return tree1是与tree2完全相同
int treeEquals(BinaryTree, BinaryTree);

/// @brief 判断一个二叉树是否是另一个二叉树的子树
/// @param subTree 第一个二叉树
/// @param tree 第二个二叉树
/// @return subTree是否是tree的子树
int isSubTree(BinaryTree, BinaryTree);

#include "./binary-tree.c"

#endif